The present invention is directed to image rotation. As will be appreciated, rotation of an image is a fundamental element of an image processing system, be it a dedicated image processing system or one that is part of a digital printer, facsimile machine, or multifunction device. The present invention is directed to a high speed method and apparatus for accomplishing the orthogonal rotation of digitized images that are represented in a run length encoded manner.
Heretofore, a patent has disclosed a general method for image rotation, the relevant portion of which may be briefly summarized as follows:
U.S. Pat. No. 5,111,514 to Ohta, issued May 5, 1992, teaches a digital image forming apparatus that may be employed to rotate characters so as to align them. In FIG. 35 and at col. 14, lines 1-25, Ohta discloses a method of character image rotation by extracting the run length data for one character image in a main scanning direction and converting it into a sub scanning direction.
In accordance with the present invention, there is provided a method, operating on a programmable data processing system, for rotating an image represented as a run length encoded data stream while decoding the run length encoded data stream, comprising: (a) resetting, in a memory associated with the data processing system, a plurality of contiguous memory locations to zero; (b) setting, in response to the run length encoded data stream, each bit in the contiguous memory indicating a beginning of each of a plurality of runs of a continuous color, wherein the bits set are ordered in a direction orthogonal to a direction in which the run length encoded data stream was encoded; and (c) resetting a register to zero; (d) exclusive ORing the contents of the register with a selected word in the contiguous memory; (e) writing the contents of the register to the selected word in the contiguous memory; and (f) selecting an immediately following contiguous memory location as the selected word and repeating steps (d) and (e) until all contiguous memory locations have been processed.
In accordance with another aspect of the present invention, there is provided apparatus for rotating a run length encoded data stream while decoding the same, comprising: a buffer for storing at least a portion of the run length encoded data stream; a cache memory comprising a plurality of contiguous memory locations; decoding means for determining the length of a run of pixels encoded in a first direction; means, responsive to the length of the run determined by said decoding means, for setting a bit in a word and bit location of said cache memory, wherein the word and bit location are determined as a function of the run length and the determined length of the run of pixels; means for EXCLUSIVE ORing a first of the contiguous memory locations with zero and writing the result thereto; means for successively EXCLUSIVE ORing each contiguous memory location with an immediately preceding contiguous memory location and writing the result to the contiguous memory location until all of the contiguous memory locations have been so processed, where the contiguous memory locations represent the rotated and decompressed image.
In accordance with yet another aspect of the present invention, there is provided a method, operating on a programmable data processing system, for rotating an image represented by a run length encoded data stream, comprising: receiving the run length encoded data stream; parsing the run length encoded data stream to determine a length of each of a plurality of runs of a continuous color; writing to a memory, in a direction orthogonal to a direction in which the run length encoded data stream was encoded, data indicating only the beginning of each of the plurality of runs of a continuous color; and repeatedly applying a logic operation to said memory to decode the run length encoded data stream in a rotated fashion.
One aspect of the invention deals with a basic problem in image processing, the fast rotation of image bitmaps. Resolution of this problem finds practical application in various image output devices where an image generated in a first orientation is constrained to be printed in an orthogonal orientation. For example, an image may be generated or scanned in a long-edge feed orientation (landscape) but printed in a short-edge feed (portrait) orientation.
This aspect is further based on the discovery of an efficient processing technique that alleviates this problem. The technique employs the compressed form of an image when it has been represented as a run length encoded bit stream to accomplish the orthogonal rotation in a computationally efficient manner. In particular, a preferred embodiment of the invention relies upon a fast rotation technique where a contiguous memory caching system is employed to facilitate the rapid rotation of the image while run length decoding the image data.
This technique can be implemented, for example, by any image processing system, be it hardware or software based. Machines implementing the invention may include printers, scanners, facsimile machines as well as multifunction machines. The hardware required preferably includes a fast cache memory and a microprocessor or similar control circuitry to control memory access (e.g., read/write) and to perform simple logic operations on the stored data.
The technique described above is advantageous because it is not only simple but efficient. The technique of the present invention avoids bit-wise processing in favor of processing run length encoded information. Furthermore, it can be adapted to any image processing system in which run length encoded data is generated or employed, making it available for use in any of a number of digital image processing systems, particularly those using run length encoding for data compression. The techniques of the invention are advantageous because they permit the highly efficient orthogonal rotation of image bitmaps. The present invention is one of a plurality of image processing operations that can be applied to compressed image formats to enable faster processing of image data in an image processing system. Some of the related techniques can be used to perform image processing while decoding a run length encoded image.